package com.Questions.DFS;

import java.util.*;
/**
 * 组合总和
 */
public class leetcode39 {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        List<Integer> combine = new ArrayList<Integer>();
        dfs(candidates,target,ans,combine,0);
        return ans;
    }

    //回溯搜索
    private void dfs(int[] candidates, int target, List<List<Integer>> ans, List<Integer> combine, int idx) {
        if(idx == candidates.length) {// 到达数组结尾
            return;
        }
        if(target == 0){// 得到答案的组合 直接返回
            ans.add(new ArrayList<Integer>(combine));
            return;
        }
        // 直接跳过
        dfs(candidates,target,ans,combine,idx+1);
        if(target - candidates[idx] >= 0) {
            combine.add(candidates[idx]);
            // 可以进行重复 的选择 因此选择的时候 偏移量不增加
            dfs(candidates,target-candidates[idx],ans,combine,idx);
            combine.remove(combine.size()-1);
        }
    }
}
